package com.hfi.leetcode;

import java.util.HashMap;

/**
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * <p>
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 * <p>
 * Example:
 * <p>
 * Given nums = [2, 7, 11, 15], target = 9,
 * <p>
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 *
 * @author ChangLiang
 * @date 2019/12/10
 */
public class TwoSum {

    /**
     * Time complexity: O(n2)
     * Space complexity:O(1)
     *
     * @param nums
     * @param target
     * @return
     */
    /*public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }*/

    /**
     * Time complexity: O(n)
     * Space complexity:O(n)
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        // 这里隐含就是会把重复值 保留第二个
        HashMap<Integer, Integer> hashMap = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i], i);
        }
        System.out.println("hashMap: " + hashMap);
        for (int i = 0; i < nums.length; i++) {
            int targetNum = target - nums[i];
            System.out.println("获取hashMap中的key: " + targetNum + " 的value: " + (hashMap.get(targetNum) == null ? "null" :
                    hashMap.get(targetNum) ) +
                    " | i " +
                    "= " + i);
            if (hashMap.keySet().contains(targetNum) && i != hashMap.get(targetNum)) {
                return new int[]{i, hashMap.get(targetNum)};
            }
        }
        return null;
    }

    /**
     * Time complexity: O(n)
     * Space complexity:O(n)
     *
     * 这个思路的根本思想仍然是 判断值在不在{@link HashMap}中的时间复杂度为O(1)
     * 每循环一个数组值，就将其需要的结果值作为key放到map中 value为此数组值的index
     * 之后循环判断下面的每个数组值在不在需要的结果map中 匹配到 就返回
     * @param nums
     * @param target
     * @return
     */
    /*public int[] twoSum(int[] nums, int target) {
        // 键为目标值减去当前元素值，索引为值
        HashMap<Integer, Integer> hashMap = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int targetNum = target - nums[i];
            Integer value = hashMap.get(nums[i]);
            System.out.println("获取hashMap中的key: " + nums[i] + " 的value: " + (value == null ? "null" : value) + " | i " +
                    "= " + i);
            if (value != null) {
                return new int[]{value, i};
            }
            // hashMap中装的 KEY是每个数组的目标值 value表示数组中的那个元素
            hashMap.put(targetNum, i);
            System.out.println("hashMap中的值: " + hashMap);
        }
        return null;
    }*/
}
